/*
 * @lc app=leetcode.cn id=51 lang=cpp
 * @lcpr version=30204
 *
 * [51] N 皇后
 */


// @lcpr-template-start
using namespace std;
#include <algorithm>
#include <array>
#include <bitset>
#include <climits>
#include <deque>
#include <functional>
#include <iostream>
#include <list>
#include <queue>
#include <stack>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
// @lcpr-template-end
// @lc code=start
class Solution {
public:
    vector<vector<string>> res; // 存储所有解

    // 检查当前位置是否可以放置皇后
    bool isValid(vector<string>& board, int row, int col, int n) {
        // 检查列是否有皇后
        for (int i = 0; i < row; ++i) {
            if (board[i][col] == 'Q') return false;
        }
        // 检查左上对角线是否有皇后
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; --i, --j) {
            if (board[i][j] == 'Q') return false;
        }
        // 检查右上对角线是否有皇后
        for (int i = row - 1, j = col + 1; i >= 0 && j < n; --i, ++j) {
            if (board[i][j] == 'Q') return false;
        }
        return true;
    }

    // 回溯函数
    void backtrack(vector<string>& board, int row, int n) {
        // 如果所有行都放置了皇后，记录解
        if (row == n) {
            res.push_back(board);
            return;
        }

        // 遍历当前行的每一列
        for (int col = 0; col < n; ++col) {
            if (!isValid(board, row, col, n)) continue; // 跳过非法位置
            board[row][col] = 'Q'; // 放置皇后
            backtrack(board, row + 1, n); // 递归处理下一行
            board[row][col] = '.'; // 回溯，撤销放置
        }
    }

    vector<vector<string>> solveNQueens(int n) {
        vector<string> board(n, string(n, '.')); // 初始化棋盘
        backtrack(board, 0, n); // 从第 0 行开始回溯
        return res;
    }
};
// @lc code=end



/*
// @lcpr case=start
// 4\n
// @lcpr case=end

// @lcpr case=start
// 1\n
// @lcpr case=end

 */

